# Problem 3
# =========
# The prime factors of 13195 are 5, 7, 13 and 29.
#
# What is the largest prime factor of the number 600851475143 ?

"""
    Generates prime numbers, in sequence, based on 
    the Sieve of Eratosthenes.
"""
def primes():
    n = 2
    primes = {}
    primes[n] = n**2
    while True:
        yield n
        n += 1
        if n in primes.values():
            while n in primes.values():
                for k,v in primes.iteritems():
                    if v == n:
                        primes[k] += k
                n += 1        
        primes[n] = n**2

n = 600851475143
#n = 13195 
#n = 100 
#n = 31 
f = primes()
p = f.next()

# and the *real* work is done here,
# but perhaps done none too efficiently
while n > 1:
    if n % p == 0:
        last_factor = p
        while n % p == 0:
            n /= p
    else:
        p = f.next()

print "-> ", last_factor 
